package cn.hdu.liang.ch4;

public class MaxSubarray {
    public static void main(String[] args) {
        int[] a = {13, -3, -25, 20,
                -3, -16, -23, 18,
                20, -7, 12, -5,
                -22, 15, -4, 7};
        int[] results = maxSubSum(a, 0, a.length-1);
        System.out.println("起始位置 : " + results[0]);
        System.out.println("结束位置 : " + results[1]);
        System.out.println("最大和   : " + results[2]);
    }

    private static int[] maxSubSum(int[] a, int low, int high) {
        if(high == low) {
            return new int[]{low, high, a[low]};
        } else {
            int mid = (low + high) / 2;
            int[] leftSum = maxSubSum(a, low, mid);
            int[] rightSum = maxSubSum(a, mid + 1, high);
            int[] crossSubSum = maxCrossSubSum(a, low, mid, high);

            if(leftSum[2] >= rightSum[2] && leftSum[2] >= crossSubSum[2]) {
                return leftSum;
            } else if(rightSum[2] >= leftSum[2] && rightSum[2] >= crossSubSum[2]) {
                return rightSum;
            } else {
                return crossSubSum;
            }
        }
    }


    private static int[] maxCrossSubSum(int[] a, int low, int mid, int high) {
        int left_sum = Integer.MIN_VALUE;
        int sum = 0;
        int max_left = mid;
        for(int i = mid; i > low; i--) {
            sum = sum + a[i];
            if(sum > left_sum) {
                left_sum = sum;
                max_left = i;
            }
        }
        int right_sum = Integer.MIN_VALUE;
        sum = 0;
        int max_right = mid + 1;
        for(int i = mid + 1; i < high; i++) {
            sum = sum + a[i];
            if(sum > right_sum) {
                right_sum = sum;
                max_right = i;
            }
        }
        return new int[]{max_left, max_right, left_sum + right_sum};
    }
}
